This page looks at some patterns in the Fibonacci numbers themselves, from the digits in the numbers
to their factors and multiples and which are prime numbers. There is an unexpected pattern in the
initial digits too. We also relate Fibonacci numbers to Pascal's triangle via the original
rabbit problem that Fibonacci used to introduce the series we now call by his name. We can also make
the Fibonacci numbers appear in a decimal fraction, introduce you to an easily learned number magic trick
that only works with Fibonacci-like series numbers, see how Pythagoras' Theorem and right-angled
triangles such as 3-4-5 have connections with the Fibonacci numbers and then give you lots of hints and
suggestions for finding more number patterns of your own.
The calculators on this page require JavaScript but you appear to have switched JavaScript off
(it is disabled). Please go to the Preferences for this browser and enable it if you want to use the
calculators, then Reload this page.
Contents of this page
The icon means there is a
You do the maths... section of questions to start your own investigations.
The calculator icon
indicates that there is a live interactive calculator in that section.
Yes!
It takes a while before it is noticeable. In fact, the series is just 60 numbers long
and then it repeats the same sequence again and again all the way through the
Fibonacci series - for ever. We say the series of final digits repeats with a cycle length of 60.
Suppose we look at the final two digits in the Fibonacci numbers. Do they have a pattern?
Michael Semprevivo suggests this investigation for you to try.
If we add all the digits of a number
we get its digit sum.
Find Fibonacci numbers for which the sum of the digits of Fib(n) is equal to
its index numbern: For example:-
Fib(10)=55
the tenth Fibonacci number is Fib(10) = 55.
The sum of its digits is 5+5 or 10 and that is also the
index number of 55 (10-th in the list of Fibonacci numbers).
So the index number of Fib(10) is equal to its digit sum.
Fib(11)=89
This time the digit sum is 8+9 = 17.
But 89 is not the 17th Fibonacci number, it is the 11th
(its index number is 11) so the digit sum of 89 is not equal to its index number.
Can you find other Fibonacci numbers with a digit sum equal to its index number?
Here are two more examples of the numbers we seek: Fib(1)=1 and Fib(5)=5.
There is also one more whose index number is less than 10 - what is it?
Can you find any more in this table of Fibonacci numbers
up to Fib(300)?
As a check, you should be able to find TEN (including those above) up to Fib(200).
How many are there up to Fib(300)?
This makes a nice exercise in computer programming so the computer does the hard work.
A more difficult question is Does this series (of Fibonacci numbers which have a digit sum
equal to their index number) go on for ever?
Robert Dawson of Saint Mary's University, Nova Scotia,
Canada summarises a simple statistical argument (originally in the article referred to below by David Terr)
that suggests there may
be only a finite number (in fact, just 20 numbers) in this series:
"The number of decimal digits in Fib(N) can be shown to be about 0.2 N,
and the average value of a decimal digit is (0+1+...+8+9)/10 = 4·5.
Thus, unless the digits of Fibonacci numbers have some so-far
undiscovered pattern, we would expect the digit sum to be about 0.9 N.
This falls further behind N as N gets larger. Fib(2222) (with 465
digits) is the largest known Fibonacci number with this property. There
are no others with N<5000, and it seems likely that Fib(2222) is
actually the largest one. However, no proof exists!"
A new research question for you to try
If you want to try a new investigation, how about converting the Fibonacci numbers
to a base other than 10 (binary is base 2 or undecimal is base 11, for example) and seeing what you
get for the digit sums in different bases. Are there any bases where the Fibonacci numbers with
a sum of their base B digits equal to their index numbers
form an infinite series? In which bases is it a finite series?
On the Sums of Digits of Fibonacci Numbers David Terr, Fibonacci Quarterly, vol. 34,
August 1996, pages 349-355.
Two series in Sloane's Encyclopedia of Integer Sequences are relevant here:
A020995 for the
index numbers and
A067515 for the
Fibonacci numbers themselves
Fibonacci Number Digit Sums Calculator
C A L C U L A T O R of Digit Sums of Fibonacci Numbers
There are some fascinating and simple patterns in the Fibonacci numbers when
we consider their factors. You might like to
click here to open a new browser window which shows the first 300 Fibonacci numbers and
their factors. It will be helpful in the following investigations:
You do the maths...
Where are the even Fibonacci Numbers?
Write down the index numbers i where Fib(i) is even.
Do you notice a pattern?
Write down the pattern you find
as clearly as you can first in words and then in mathematics.
Notice that 2=F(3) also.
Now find where there are Fibonacci numbers which are multiples of 3.
and again write down the pattern you find in words and then in mathematics.
Again notice that 3=F(4).
What about the multiples of 5? These are easy to spot because they
end with 0 or 5.
Again, write down the pattern you find.
You can try and spot the multiples of 8, if you like now.
Why 8? Because
we have found the multiples of 2, then 3, then 5 and now 8 is the next Fibonacci number!
Do you think your patterns also have a pattern? That is, for
any Fibonacci Number F can you tell me where you think all its multiples will
appear in the whole list of Fibonacci Numbers?
So every Fibonacci number is a factor of (an infinite number of) Fibonacci numbers,
that is:
Fibonacci numbers as Factors of Fibonacci numbers
i
3
4
5
6
7
8
9
10
11
12
...
Fib(i)
2
3
5
8
13
21
34
55
89
144
...
F a c t o r s
2=Fib(3)
Every 3rd Fib number
3=Fib(4)
Every 4th Fib number
5=Fib(5)
Every 5th Fib number
8=Fib(6)
Every 6th Fib number
F(k)
...
F(all multiples of k)
Putting this into words we have:
Every 3-rd Fibonacci number is a multiple of 2 i.e. a multiple of F(3)
Every 4-th Fibonacci number is a multiple of 3 i.e. a multiple of F(4)
Every 5-th Fibonacci number is a multiple of 5 i.e. a multiple of F(5)
Every 6-th Fibonacci number is a multiple of 8 i.e. a multiple of F(6)
which suggests the general rule:
Every k-th Fibonacci number is a multiple of F(k)
or, expressed mathematically,
F(nk) is a multiple of F(k) for all values of n and k from 1 up.
A nice factorisation of F(2n)
If we apply the above to F(2) which is 1, we get that 1 is a factor of every Fibonacci numbers - which is not particularly useful!
There is a more interesting result here though. Have a look at this table and see if you can spot the pattern:
2i
2
4
6
8
10
12
...
Fib(2i)
1
3
8
21
55
144
...
F(i)
1
1
2
3
5
8
...
F(2i)/F(i)
1
3
4
7
11
18
...
Can you find a pattern in the factors on the bottom row? (Hint: They are the sum of two Fibonacci numbers).
These new numbers turn out to be very important in formulae for Fibonacci numbers. They are called the
Lucas Numbers: L(n) and have many interesting properties in their own right.
F(2n) is a multiple of F(n)
F(2n) = F(n) L(n) where
L(n) are the Lucas numbers: L(n) = F(n−1) + F(n+1)
This section was suggested by Peter Bendall, March 2021
A Primer For the Fibonacci Numbers: Part IX
M Bicknell and V E Hoggatt Jr in The Fibonacci Quarterly
Vol 9 (1971) pages 529 - 536 has several proofs that F(k) always divides
exactly into F(nk): using the Binet Formula; by mathematical induction
and using generating functions.
A free book with the whole collection of parts of the Primer is available online
as a PDF or as separate parts
from the Fibonacci Association.
Every number is a factor of some Fibonacci number
But what about numbers that are not Fibonacci numbers?
Which other numbers exactly divide into (are factors of) Fibonacci numbers?
The surprising answer is that
there are an infinite number of Fibonacci numbers with any given number as a factor!
For instance, here is a table of the smallest Fibonacci numbers that have each of the integers from 1 to 13 as a factor:
This index number for n is called the Fibonacci Entry Point of n.
Since Fib(15) is the smallest Fibonacci number with 10 as a factor, then, using the result of the previous section, we then know that
Fib( any multiple of 15 ) also has 10 as a factor
thus Fib(15), Fib(30), Fib(45), Fib(60), ..., Fib(15k), ... all have 10 as a factor.
This applies to all numbers n as the factor of some Fibonacci number.
Here is a graph of the series, the
index number i of the first Fibonacci number that has a factor of n for n up to various values:
Show the graph up to n=
25
100
250
500
1000
3000
The Fibonacci Series beginning 0,1,1,... is the only (general) Fibonacci sequence beginning a,b,a+b,... which has all the
primes as factors of some number in the series. This was proved by Brother U Alfred in the reference.
Primes which are factors of all Fibonacci sequences,Brother U Alfred, Fib Quart, 2 (1964),
pages 33-38. PDF
If we take each number n = 1,2,3,... and find the smallest i for which Fib(i) has n as
a factor, we obtain this series of index (i) values:
1,3,4,6,5,12,8,6,12,15,10,12,7,24,20,12,9,12,18,30,8,30,... is
Sloane's
A001177
An early reference for the theorem that every number is a factor of some Fibonacci number
seems to be N N Vorob'ev in his Fibonacci Numbers booklet,
published by Pergamon in 1961 where a proof is also given.
Also, he showed that the first Fibonacci number with a factor i will be found within the first i2
Fibonacci numbers and thereafter at double, treble etc.. that index number.
The original version is in Russian, Chisla fibonachchi, 1951 and it is now again in print as
Fibonacci Numbers, N N Vorob'ev, Birkhauser (Jan 2003).
TheFibonacci Series Modulo m D. D. Wall, The American Mathematical
Monthly (1960) pages 525-532
is the earliest and most comprehensive paper on the subject of Fibonacci factors and Pisano periods.
Wall uses:
k(m) for the Pisano period of the Fibonacci numbers modulo m
h(a,b,m) for the Pisano period of the General Fibonacci sequence G(a,b,n) modulo m
In the following sections we use the name FEP(n) for the Fibonacci Entry Point of n,
the smallest index of a Fibonacci number that has n as a factor and look at some patterns and special cases.
Are there any numbers n where FEP(n) = n?
There are some numbers such as 5 that are also their own entry points since
Fib(5) = 5 is the first Fibonacci number with an factor of 5. Are there others?
Yes! For instance Fib(12) = 144, the twelfth Fibonacci number
is the first one with a factor of 12.
A list of those values of n where FEP(n) = n with n up to 1000 is
1, 5, 12, 25, 60, 125, 300, 625
This is a combination of two series which becomes clear if you factorize each of these numbers.
Can you find the next two numbers?
1500, 3125
FEP(n) = n – 1
Fib(10) = 55 = 11 × 5 so the tenth is the first Fibonacci number with 11 as a factor: FEP(11) = 10.
Fib(18) = 2584 = 19 × 136 so the 18th Fibonacci number is the first with 19 as a factor: FEP(19) = 18
The list of the first n where FEP(n) = n – 1 is:
11, 19, 31, 59, 71, 79, 131, 179, 191, ... A106535
Is there a formula for these values?
Brother U Alfred showed that all these terms end in 1 or 9:
Primes which are factors of all Fibonacci sequences,Brother U Alfred, Fib Quart, 2 (1964),
pages 33-38.
FEP(n) = n + 1
There is also a sequence of numbers with an FEP just one more than the number itself: i.e. FEP(n) = n + 1:
for instance
3 is a factor of Fib(4) = 3 and
7 is a factor of Fib(8) = 21
and the list of the first few n where FEP(n) = n + 1 is:
2, 3, 7, 23, 43, 67, 83, 103, 127, 163, 167, ... A000057
All these values end in 3 or 7 but is there a formula for these?
Factoring shows that all these are prime.
Brother U Alfred showed that all these terms end in 3 or 7 - see the reference in the previous section.
FEP(n) = n + 5
Benoit Cloitre noticed a connection between the n where FEP(n) = n + 1 and those n with FEP(n) = n + 5:
FEP(n) = n + 5: n=
10
15
35
115
215
335
415
515
635
...
FEP(n) = n + 1: n=
2
3
7
23
43
67
83
103
127
...
Can you find the connection?
Factor the FEP(n) = n + 5 values
Other patterns in FEP(n)
There are also many other patterns in FEP(n). Here, for instance, are the equations of some of straight lines that lie on or near
apparent lines of points in
one of the graphs above:
It looks as if for any n, FEP(n) ≤ 2n but the only proof we have is that
FEP(n) ≤ n2 in the Vorob'ev reference above.
Earlier we saw that every number is a factor of some Fibonacci number, the first index number being called the FEP of
that number.
Once we know the index number of the first Fibonacci number with n as a factor, FEP(n), then all the multiples of that index
are also Fibonacci numbers with n as a factor. This since FEP(24) is 12, then Fib(12) has a factor of 24 and so does
Fib(24), Fib(36), Fib(48), etc.
So now we can ask the question:
Which Fibonacci numbers Fib(n) have n as a factor?
For instance F(12)=144 which has 12 as a factor;
F(25)=75025 which has 25 as a factor;
but F(15)=610 which does not have 15 as a factor.
Here are the first few Fibonacci numbers F(n) with n as a factor:
n
Fib(n)
=
n
×
m
1
1
=
1
×
1
5
5
=
5
×
1
12
144
=
12
×
12
24
46368
=
24
×
1932
25
75025
=
25
×
3001
36
14930352
=
36
×
414732
The series of indices of such Fibonacci numbers is:
Can you identify which numbers are in this sequence?
It is the union of two subsequences:
F(5m): F(0)=1, F(5)=5, F(52)=F(25)=75025, ...
and any of these multiplied by any number of 5's: 5kF(5m): A129066
12n where F(12n) is a multiple of 12n: 12 times {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, ...
A072378}
Fibonacci numbers where i ± 1 is a factor of Fib(i)
i–1 is a factor of F(i)
i
Prime factors of F(i)
i–1
the rest
2
1
1
3
2
1
4
3
1
8
7
3
14
13
29
18
17
23×19
24
23
25×32×7
38
37
113×9349
44
43
3×89×199×307
48
47
26×32×7×23×1103
54
53
23×17×19×109×5779
68
67
3×1597×3571×63443
74
73
149×2221×54018521
84
83
24×32×13×29×211×281×421×1427
98
97
13×29×6168709×599786069
Fibonacci index numbers i where Fib(i) has i–1 as a factor:
2, 3, 4, 8, 14, 18, 24, 38, 44, 48, 54, 68, 74, 84, 98, 104, ... A100993
Though all the i listed here are one more than a prime (i-1 is prime), this is not true in general. The smallest such
is 324, which has 323 as a factor of Fib(324) but 323=17×19. See the notes on A100993 in the link.
i+1 is a factor of F(i)
i
Prime factors of F(i)
i+1
the rest
10
11
5
18
19
23×17
28
29
3×13×281
30
31
23×5×11×61
40
41
3×5×7×11×2161
58
59
19489×514229
60
61
24×32×5×11×31×41×2521
70
71
5×11×13×29×911×141961
78
79
23×233×521×859×135721
88
89
3×7×43×199×263×307×881×967
100
101
3×52×11×41×151×401×3001×570601
108
109
24×34×17×19×53×107×5779×11128427
130
131
5×11×233×521×2081×24571×14736206161
Fibonacci index numbers i where Fib(i) has i+1 as a factor:
10,18,28,30,40,58,60,70,78,88,100,108,130,138,... A100992
All these i are one less than a prime (i+1 is prime) this is not always true. The smallest such
is 441 since 442 is a factor of Fib(441) and 442 is not prime.
Are there any more patterns hidden here in the factors of Fibonacci numbers?
If so, let me know (click on Dr Ron Knott at the foot of this page for
contact details) and I'll try to include some of them here.
Another variation is to look at the remainder when we divide Fib(i) by i.
Which index numbers, i, when we divide Fib(i) by i, have a remainder of 1?
For example, the smallest is Fib(2)=1 which obviously has a reminder of 1 when we divide Fib(2) by 2;
the next is Fib(11)=89 which, when we divide 11 leaves a remainder of 1.
So your answer should start 2, 11, ...1,2,11,19,22,29,31,38,41,58,59,... A023173
What about those index numbers i where Fib(i) has a remainder of 1 less than i when Fib(i) is divided by i?
This time we start again with Fib(2)=1 since it leaves a remainder of 2-1 when we divide it by i=2;
Also Fib(3)=2 and Fib(4)=3 are also one less than their index numbers and the next is
Fib(7)=13 which leaves a remainder of 7-1=6 when we divide 13 by 7.
So this time your answer starts: 1, 2, 3, 4, 7, ...
1,2,3,4,7,13,14,17,23,26,34,37,43,46,47, ... A023162
Above we looked at all n and which was the first Fibonacci number for which that n was a factor.
In this section, we concentrate only on those n which are prime numbers.
If we look at the prime numbers and ask when they first appear as a factor of a
Fibonacci number, we find they do so within the
first p+1 Fibonacci numbers. In this table, i is the index of the first Fibonacci number that
has the prime as a factor:
Prime p
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
first index i
3
4
5
8
10
7
9
18
24
14
30
19
20
44
16
27
58
15
68
70
The first-index numbers seem to be either equal to the prime (as for p=5) or one less (as p=11) or 1 more (p=7)
in many cases. What about the others?
They are factors of p+1 (as in the case of p=17 where 9 is a factor of p+1=18)
or of p–1 (e.g. p=29 where the index 14 is a factor of p-1=28).
This is true in general.
This series on the lower row: 3,4,5,8,10,7,9,18,24,14,30,19,20,44,16,27,58,15,68,70,...
is Sloane's A001602.
It is a subsequence of A001177 above, selecting the numbers at the prime positions.
The smallest Fibonacci number which has the nth prime as a factor gives
the series: 2, 3, 5, 21, 55, 13, 34, 2584, ... which is
A051694. But as these
Fibonacci numbers get large rapidly, it is easier to use the index numbers of such Fibonacci
numbers to get the series above (A001602).
Vajda (reference at foot of this page), on page 84 states:
Let F(u), u > 0, be the smallest Fibonacci number divisible by
the prime p.
The subscript u is called the rank of apparition of p,
and we know that it is a factor of, or equal to, p–1 or p+1.
An alternative name is the Fibonacci entry point (FEP) and this applies to any number, not just the primes.
On another of Ron Knott's Maths pages we look at the Lucas numbers, a series of numbers with the same rule
as the Fibonacci numbers but starting with 2 and 1. In many senses Lucas numbers and Fibonacci numbers
are twin series.
Fibonacci common factors
One of the fundamental divisibility properties of Fibonacci numbers concerns factors common to two Fibonacci numbers.
If a number is a factor of both F(n) and F(m) then it is also a factor of F(m+n).
This is a consequence of the formula:
But this is also part of a more general result about factors common to two Fibonacci numbers.
If g is the greatest divisor of bothF(m) and F(n) then it is also a Fibonacci number. Which Fibonacci number? Its index number is the greatest divisor common to the two indices m and n!
If we use gcd(a,b) to mean the greatest common divisor (factor) of
a and b then we have:
gcd( F(m), F(n) ) = F( gcd(m,n) )
This result is Theorem 11 in
Fibonacci Numbers, N N Vorob'ev (2003 translation of the 1951 Russian original).
This section was suggested by an email from Allyn Shell.
Neighbouring Fibonacci Numbers have no common factors
You might have noticed that no even Fibonacci number is next to another even Fibonacci number,
or, no two neighbouring Fibonacci's have a common factor of 2.
In the last section we saw that Fib(3)=2 so we would expect the even Fibonacci numbers (with a factor of 2)
to appear every at every third place in the list of Fibonacci numbers.
The same happens for a common factor of 3, since such Fibonacci's are at every 4-th place (Fib(4) is 3).
In fact, there will not be a Fibonacci number as a common factor between two neighbouring
Fibonacci's for the same reason.
But what about other numbers as factors such as 6 or 7?
The answer is that no number (bigger than 1) is a factor of two neighbouring Fibonacci numbers.
Two numbers that have no common factors are called relatively prime (to each other).
There is a proof of this that Tom E Ace wrote to me about -- and it is so simple!
If A and B have a common factor then it must also be a factor of A+B.
If A and B have no common factor, then neither do B and A+B
for if B and A+B had a common factor, then their difference would too but their difference is just A.
So in any Fibonacci-type series which starts with A and B, if A and B are relatively prime then so
are all pairs of consecutive numbers in the series.
Alternatively, if A and B have a common factor then so do B and A+B (the next pair in the series)
and so on, so that this factor is a factor of all numbers in the series.
Since F(1)=1 and F(2)=1 have no common factor, then no neighbouring pairs in the Fibonacci series have a common factor.
We have just shown
that
F(n) and F(n+1) are relatively prime.
Now let's look at Fibonacci numbers that have no factors at all (apart from 1 and themselves of course), the prime Fibonacci numbers:
We have seen from investigations above that F(nk) is a multiple of F(k) for all values of n
and k = 1,2,...
This means that if the subscript has factors (i.e. is composite, is not a prime) then so
is that Fibonacci number -- with one exception: can you find it?
So what about those Fibonacci numbers with no factors (apart from 1 and itself, of course)?
These are the Fibonacci numbers that are primes.
We can now deduce that
Any Fibonacci number that is a prime number must also have a subscript that is a prime number
again with one little exception - can you find it?
Hint: you won't have to search far for it
.
Searching across the list of index numbers, i, for which Fib(i)
is prime begins as follows:
i
3
4
5
7
11
13
17
23
29
43
47
83
F(i)
2
3
5
13
89
233
1597
28657
514229
433494437
2971215073
99194853094755497
Now you should be able to spot the odd one out:
that one number, i, which is not a prime in the list above,
even though Fib(i) is.
The series continues (updated January 2007):
i
Fib(i)
Number of digits
Prime?
131
10663404174...72169
28
137
19134702400...23917
29
359
47542043773...76241
75
431
52989271100...62369
90
433
13872771278...68353
91
449
30617199924...65949
94
509
10597999265...29909
107
569
36684474316...65869
119
571
96041200618...74629
119
2971
35710356064...16229
621
4723
50019563612...91957
987
5387
29304412869...55833
1126
9311
34232086066...76289
1946
9677
10565977873...70357
2023
14431
35575535439...75869
3016
25561
38334290314...14961
5342
30757
30434499662...75737
6428
35999
99214776140...24001
7523
37511
96802910427...75089
7839
Jun 2005
50833
13159270824...02753
10624
Oct 2005
81839
97724940760...46561
17103
104911
5660323637...84189
21925
?
130021
2706998033...75321
27173
?
148091
6904738850...74809
30949
?
201107
3371962609...27913
42029
?
397379
8912712429...66921
83047
?
433781
3296782330...74981
90655
?
590041
8448035604...82641
123311
?
593689
2059052250...74289
124074
?
604711
5962634693...37389
126377
?
Those marked are definitely prime;
those marked? are probably prime
but have not been proved so (explained here).
There are Fibonacci numbers with a prime-number subscript but they are not prime, for example:
19 is prime but F(19) = 4181 = 113 × 37.
Every Fibonacci number is marked in a special way.
If we look at the prime factors of a Fibonacci number, there will be at least one of them that has never before appeared as a factor
in any earlier Fibonacci number.
This is known as Carmichael's Theorem and applies to all Fibonacci numbers except 4 special cases:
Fib(1)=1 (has no prime factors),
Fib(2)=1 (has no prime factors),
Fib(6)=8 which only has prime factor 2 which is also Fib(3),
Fib(12)=144 which also only 2 and 3 as its prime factors and these have appeared earlier as Fib(3)=2 and Fib(4)=3.
Apart from these special cases, the theorem is true for all Fib(n).
Those prime factors that have never appeared earlier in the table are shown
like this.
Here is the first part of a table of Fibonacci numbers and their prime factors:
The first 25 Fibonacci numbers Factored
n : F(n)=factorisation
0 : 0 =
1 : 1 =
2 : 1 =
3 : 2 PRIME
4 : 3 PRIME
5 : 5 PRIME
6 : 8 = 23
7 : 13 PRIME
8 : 21 = 3 x 7
9 : 34 = 2 x 17
10 : 55 = 5 x 11
11 : 89 PRIME
12 : 144 = 24 x 32
13 : 233 PRIME
14 : 377 = 13 x 29
15 : 610 = 2 x 5 x 61
16 : 987 = 3 x 7 x 47
17 : 1597 PRIME
18 : 2584 = 23 x 17 x 19
19 : 4181 = 37 x 113
20 : 6765 = 3 x 5 x 11 x 41
21 : 10946 = 2 x 13 x 421
22 : 17711 = 89 x 199
23 : 28657 PRIME
24 : 46368 = 25 x 32 x 7 x 23
25 : 75025 = 52 x 3001
[See the whole list up to Fib(300) on the next web page
in a new window.]
A Result about the Primes Dividing Fibonacci Numbers by M S Boase in Fibonacci Quarterly vol 39 (2001),
pages 386-391 contains a proof of this result but does not refer to it as Carmichael's Theorem. The problem is traced
back to an analogous result proved by K Zsigmondy in 1892.
A Simple Proof of Carmichael's Theorem on Primitive Divisors
by M Yabuta in Fibonacci Quarterly vol 39 (2001), pages 439-443 also contains a proof and refers to the following article...
On the Numerical Factors of the Arithmetic Forms
αn±β
n by R D Carmichael in Annals of Maths vol 15 (1913) pages 30-70,
where Carmichael refers to such first-occurrence-prime-factors as characteristic factors
Fib(prime) and Carmichael's Theorem
Shane Findley of Dover, USA, points out that all the factors of Fib(p)
when p is a prime number are characteristic prime factors.
Let's have a look at what this means in terms of our Table of Fibonacci Factors.
This relies on two properties of Fib(i) that we have already seen (on this page):
In the Factors of Fibonacci Numbers section we saw that
if i itself has a factor k (so that we can write i as nk)
then Fib(nk) has Fib(k) as a factor also.
Also, if Fib(i) is a prime number then i itself must be prime - see the
Fibonacci Primes section.
So if i is prime - and let's call it p here to remind ourselves we are considering the special case of
Fib(i) for a prime number i - then p will
have no factors and therefore Fib(p) also can have no earlier Fibonacci numbers as its factors.
Note that this does not mean Fib(p) itself must be prime, only that no smaller Fibonacci number
can be a factor.
We found an example of this in Fib(19) which is 4181 = 37 x 113, and, although 19 is a prime number, Fib(19) is not.
Carmichael's Theorem says that there are special prime factors of Fib(p) that have not
occurred earlier in our list of Fibonacci numbers.
So, if p is a prime number, then
either Fib(p) is prime - in which case this is the first time we have seen this prime number
in the list of Fibonacci factors
or else, if Fib(p) has factors, at least one of them is new - a characteristic factor.
But Shane's observation is that all the prime factors of Fib(p) are characteristic factors!
To put this more simply
for a prime number p, Fib(p) is either
a prime itself or
is a product of prime factors that all appear to be characteristic
(appear for the first time in our list of Fibonacci factors).
Here is a selection of lines from the Factors Table for
those Fib(i) where i is a prime number.
You will notice that either they are prime numbers or else their factors are all
shown like this to show they are characteristic factors:
The Fibonacci Numbers Fib(p)
where p is a prime number less than 100
n : F(n)=factorisation
2 : 1
3 : 2 PRIME
5 : 5 PRIME
7 : 13 PRIME
11 : 89 PRIME
13 : 233 PRIME
17 : 1597 PRIME
19 : 4181 = 37 x 113
23 : 28657 PRIME
29 : 514229 PRIME
31 : 1346269 = 557 x 2417
37 : 24157817 = 73 x 149 x 2221
41 : 165580141 = 2789 x 59369
43 : 433494437 PRIME
47 : 2971215073 PRIME
53 : 53316291173 = 953 x 55945741
59 : 956722026041 = 353 x 2710260697
61 : 2504730781961 = 4513 x 555003497
67 : 44945570212853 = 269 x 116849 x 1429913
71 : 308061521170129 = 6673 x 46165371073
73 : 806515533049393 = 9375829 x 86020717
79 : 14472334024676221 = 157 x 92180471494753
83 : 99194853094755497 PRIME
89 : 1779979416004714189 = 1069 x 1665088321800481
97 : 83621143489848422977 = 193 x 389 x 3084989 x 361040209
No primes next to Fibonacci's!
Let's look at the numbers next to each Fibonacci number...
n
3
4
5
6
7
8
9
10
11
12
13
...
Fib(n)
2
3
5
8
13
21
34
55
89
144
233
...
Fib(n)±1
1 3
2 4
4 6
7 9
12 14
20 22
33 35
54 56
88 90
143 145
232 234
...
We see there are a few small Fibonacci numbers which have a prime neighbour
(shown like this)
but then they seem to stop. (143=11x13 is not a prime.)
Is this just a fluke or a feature of all but a few initial Fibonacci numbers -
that their neighbours are never prime?
Toby Gee, a student at John of Gaunt's School, Trowbridge proved this in the 1996/97 (see the references at the end of this section).
He gave formulae for the factors too:
For the Fibonacci numbers with even index numbers, that is F(2n), we have:-
F(2n) + (–1)n
=
( F(n+2) + F(n) ) F(n–1)
F(2n) – (–1)n
=
( F(n) + F(n–2) ) F(n+1)
and for the odd index numbers, F(2n+1), we have similarly:
Letter from Toby Gee
in Mathematical Spectrum, vol 29 (1996/1997), page 68.
Greatest Common Divisors in Altered Fibonacci Sequences U Dudley, B Tucker
Fibonacci Quarterly 1971, pages 89-91 give these formulae too in an expanded form.
Almost no primes next to Fibonacci's powers either!!
So having seen that the Fibonacci numbers influence their neighbours so that no neighbour
is prime, what about neighbours of the squares of Fibonacci numbers?
Two formulae answer our question immediately:
F(n)2 + 1 =
{
F(n – 2)F(n + 2) if n is odd
F(n – 1)F(n + 1) if n is even
F(n)2 – 1 =
{
F(n – 1)F(n + 1) if n is odd
F(n – 2)F(n + 2) if n is even
These two formulae tell us that
the neighbours of F(n)2 are never prime,
in fact they are always the product of two Fibonacci numbers!
So we could now investigate the neighbours of the
cubes of Fibonacci Numbers
and indeed I will leave you to discover the formulae that apply in those cases. You will find that they too are never prime!!
Spoiler:
The general result was found by Vernon Hoggatt Jr and Marjorie Bicknell-Johnson in 1977.
The smaller neighbour of every power of every Fibonacci number (beyond F(3)=4)
is always composite.
This is easy to see with a little algebra since xn – 1 always has x – 1 as a factor no matter
what number x is.
For the larger neighbour of a power of a Fibonacci number,
all of them are again composite
except in one special case: when the power is itself a power of 2 (that is, it is 4, 8, 16, 32, ...)
AND also the Fibonacci index number is a multiple of 3. In this case the number may be prime!
For example, all these neighbours on the "+1" side of a power of a Fibonacci number
are prime:
You will see that all the powers are themselves powers of 2 and all the indices
are multiples of 3. It seems that such primes are quite rare though.
So Fibonacci numbers exert a powerful influence
in that they (almost always) make any number next to them or their powers
factorize!
Composites and Primes Among Powers of Fibonacci Numbers increased or
decreased by one V E Hoggatt Jr and M Bicknell-Johnson,
Fibonacci Quarterly vol 15 (1977), page 2.
A Prime Curio
G. L. Honaker Jr. pointed me to a little curio about the Fibonacci and the prime numbers:
that the number of primes less than 144, which is a Fibonacci number, is 34, also a Fibonacci number.
He asks:
Can this happen with two larger Fibonacci numbers?
I pass this question on to you - can it? The link to the Prime Curio page
uses the notation that
(N) means the number of
primes between 1 and N
and includes N too if N is prime. (See also
a graph of this function.)
Since the prime numbers begin
2, 3, 5, 7, 11, 13, 17, ...
then (8)=4 (there
are 4 primes between 1 and 8, namely 2, 3, 5 and 7) and
(11)=5.
Here are some smaller values that are also Fibonacci numbers:
(2) = 1 (3) = 2 (5) = 3 (21) = 8
Another Prime Curio
M J Zerger
noticed that the four consecutive Fibonacci numbers:
F(6)=13, F(7)=21, F(8)=34 and F(9)=55 have a product of 13x3x7x17x2x5x11 or
rearranging the factors into order: 2x3x5x7x11x13x17
which is the product of the first seven prime numbers!
More Links and References on Prime Numbers
There is a complete list of all Fibonacci numbers and their factors up
to the 1000-th Fibonacci and 1000-th Lucas numbers and partial results beyond that
on
Blair Kelly's Factorisation pages Archived
(originally http://mersennus.net/fibonacci/)
For the real enthusiast,
join the Yahoo
group on the PrimeForm
computer program and related matters to primes. Its Files folder
has a section on Lucas and Fibonacci primes.
See Neil Sloane's
Online Encyclopedia of Integer Sequences
where series number
A001605
is the series of i's for which Fib(i) is known to be prime: 3,4,5,7,11,13,17,23,29,...
and contains fairly up-to-date information on the latest results.
Factorization of Fibonacci Numbers D E Daykin and L A G Dresel in The Fibonacci Quarterly, vol 7
(1969) pages 23 - 30 and 82 gives a method of factoring a Fib(n) for composite n
using the "entry point" of a prime, that is, the index of the first Fibonacci number
for which prime p is a factor.
Mathematics Teacher M J Zerger vol 89 (1996) page 26
which repeats after 60 digits.
These are the remainders of the Fibonacci numbers when we divide by 10, or,
to use the mathematical term, Fibonacci numbers modulo 10. x modulo n means the remainder when we divide the whole number x by n
and it is also written as x mod n for short. You may also see
x ≡ a (n) meaning x mod n is a.
The final two digits are therefore the Fibonacci numbers mod 100:
and this cycle repeats after 300 numbers.
The final three
digits are the Fibonacci's mod 1000 with a cycle length of 1500, and so on.
If we look at the Fibonacci numbers mod 2, then we get either 0 or 1 as these are
the only two remainders we can have on dividing by 2. However, if the number is even the remainder
is 0 and if it is odd the remainder is 1. This is called the parity of a number x
and so x mod 2 tell us if x is even or odd.
For the Fibonacci numbers we have:
We will always get a cycle that repeats!
The reason is that there are only a finite number of remainders when we divide by N:
the values 0, 1, 2, ..., N-1 (N of them) and therefore there are a finite number of pairs
of remainders (N2) so when we keep adding the latest two Fibonacci's to get the
next, we must eventually get a pair of remainders that we have had earlier and the cycle will repeat
from that point on.
Here are the Fibonacci numbers mod 3:
so the cycle-length of the Fibonacci numbers mod 3 is 8.
For the divisors (moduli) 2, 3, 4, 5, and so on we have the following cycle lengths for the Fibonacci Numbers:
The Pisano periods can be at most 6 times the modulus with examples shown in red in the table above.
This is only achieved for moduli that are twice a power of 5:
Apart from modulo 2, all the cycle lengths are even.
For mod 2 the cycle is 0,1,1, 0,1,1, ... of length 3
There are some numbers n where the length of the cycle mod n is n itself, called fixed points,
for example the Fibonacci numbers mod 24 are 0,1,1,2,3,5,8,13,21,10,7,17,0,17,17,10,3,13,16,5,21,2,23,1 which then repeats
so the cycle has length 24: Pisano(24) = 24.
The series of these fixed points of the Pisano function is
(1,) 24, 120, 600, 3000, 15000, 75000, 375000, ... A235702
The entries are all of the form 24×5n so that starting with 24 each
of the following is 5 times the previous one.
Look at this table of Pisano periods of n, 2n, 3n, ... :
Pisano
n
2n
3n
4n
5n
6n
7n
n=2
3
6
24
12
60
24
48
n=3
8
24
24
24
40
24
16
n=4
6
12
24
24
60
24
48
n=5
20
60
40
60
100
120
80
Can you see that Pisano(kn) is a multiple of Pisano(n) for each of these n?
This can be proved true for all n - see Marc's page as mentioned above.
So if n divides m which we write as n | m then Pisano(n) | Pisano(m).
Using the last result, if we find the prime factors of n,
n = p1a1 p2a2 ...
then Pisano(n) will be the lowest common multiple (LCM) of all the Pisano(piai).
What can we say about Pisano(pa) for a prime p? Wall conjectured in 1960 (see references) that
Pisano(pa) = pa–1Pisano(p) for all primes p.
This still seems to be unproven.
If it is true, it means that we can find Pisano(n) for all n once we know Pisano(p) for all primes p that are (prime) factors of n.
(see A060305)
Here is a table of the Pisano periods for the first 15 primes:
Is there a formula for the cycle lengths of the Fibonacci Numbers?
Not quite! It seems to depend on the factorization of the divisor and the following article is an excellent summary:
Notes 88.52: Some Properties of finite Fibonacci Sequences D Vella, A Vella
Mathematical Gazette 88 (2004) pages 494-499.
Dominic Vella's
Mathematics page. Dominic and Alfred Vallas continue to do research on the Fibonacci numbers mod n
and generalised Fibonacci numbers mod n.
That the remainders of the Fibonacci numbers when divided by a certain number is a cycle seems to have been
known even to the French mathematician (though he was born in Italy in Turin)
Joseph Louis Lagrange (1736-1813) as early as 1774: Oeuvres de LaGrange, published in Paris in 1877, pages 5-182.
However, the numbers were not then called the Fibonacci Numbers and their periods were not called Pisano periods!
Fibonacci Series Modulo m D D Wall, The American Mathematical Monthly, Vol. 67, No. 6 (Jun. - Jul., 1960),
pages 525-532.
There are many interesting relationships in the Pisano Periods sequence (the series of cycle lengths for modulus 2 upwards). Here is a table of the cycle lengths (the Pisano periods) for some smaller moduli:
Add the row label to the column label
to find N and the entry for that row and column is the Pisano period for modulus N:
Pisano Periods for moduli 2 - 299
+
0
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
260
270
280
290
0
.
60
60
120
60
300
120
240
120
120
300
60
120
420
240
600
240
180
120
180
600
240
60
240
120
1500
420
360
240
420
1
.
10
16
30
40
72
60
70
216
112
50
152
110
130
32
50
48
72
90
190
136
42
252
80
240
250
168
270
56
392
2
3
24
30
48
48
84
30
24
120
48
72
48
60
120
210
36
216
264
336
96
150
108
456
84
330
48
390
72
96
444
3
8
28
48
40
88
108
48
148
168
120
208
76
40
144
140
72
328
348
120
388
112
280
448
52
648
240
176
112
568
588
4
6
48
24
36
30
72
96
228
48
96
84
72
30
408
24
240
120
168
48
588
72
72
48
168
60
768
120
276
210
336
5
20
40
100
80
120
20
140
200
180
180
80
240
500
360
140
60
40
400
380
280
40
440
600
160
560
360
540
100
360
580
6
24
24
84
24
48
48
120
18
264
48
108
42
48
36
444
168
168
120
120
336
624
72
228
174
120
384
144
48
420
228
7
16
36
72
76
32
72
136
80
56
196
72
168
256
276
112
316
336
232
180
396
48
240
456
312
252
516
88
556
80
360
8
12
24
48
18
24
42
36
168
60
336
72
174
192
48
228
78
48
132
96
120
168
108
72
144
60
264
408
138
48
444
9
24
18
14
56
112
58
48
78
44
120
108
144
88
46
148
216
364
178
144
22
90
296
114
238
168
304
268
120
612
336
The relationship between the Pisano Period mod n and FEP(n)
If the initial digits of the Fibonacci series form a cycle of length 60 (the Pisano period of 10)
then Fib(60) is the same as Fib(0), which is 0. So Fib(60) has the same remainder mod 10, namely 0,
so 10 divides exactly into Fib(60).
The same is true for all Pisano periods mod n: if the Pisano period mod n is P then Fib(P) has n as a factor.
However, Pisano(n), the Pisano period mod n, may not be the first
Fibonacci number which has n as a factor: for example
the Fibonacci numbers mod 3 have a cycle of length 8, so that Fib(8)=Fib(0) mod 3, and in general
Fib(n)=Fib(n+8) mod 3:
i
0
1
2
3
4
5
6
7
8
9
...
Fib(i)
0
1
1
2
3
5
8
13
21
34
...
Fib(i) mod 3
0
1
1
2
0
2
2
1
0
1
...
For 3, there are two 0s in each Pisano cycle of length 8.
Earlier on this page we looked at where a given number first appears
as a factor of a Fibonacci number: the Fibonacci Entry Point for that number or FEP(n).
So the Pisano period Pisano(n) for n may be the index number of the first Fibonacci
number to have n as a factor -- or it may be some multiple of it.
In fact, it can be proved that the Pisano period Pisano(n) is either
equal to the Fibonacci entry point: Pisano(n)=FEP(n) or
Pisano(n) is twice FEP(n) or
Pisano(n) is four times FEP(n)
FEP(n) versus Pisano(n)
n
2
3
4
5
6
7
8
9
10
11
12
13
...
Pisano(n)
3
8
6
20
24
16
12
24
60
10
24
28
...
FEP(n)
3
4
6
5
12
8
6
12
15
10
12
7
...
Pisano(n) FEP(n)
1
2
1
4
2
2
2
2
4
1
2
4
...
Since F(n) is a factor of F(kn) for all k, then the final row here tells us how many zeroes there are in the
Pisano cycle mod n. See A001176.
If n itself is a Fibonacci number bigger than 2, as with 5, 8 and 13 in the table here, then this quotient
is alternately 2 and 4, that is
Pisano(Fib(2n))=2 and Pisano(Fib(2n+1))=4
with our usual system
of indexing Fibonacci which begins Fib(0)=0 and Fib(1)=1.
And here are some investigations to get you started discovering some of
the Pisano period's
fascinating properties:-
You do the maths...
What is special about the cycle lengths of moduli 2, 4, 8, 16, 32, 64, ...?
Does the same thing happen with the powers of 3: 3, 9, 27, 81, ...?
Take pairs of prime numbers such as 3 and 5 or 3 and 13 etc... Find the Pisano period of each in the pair. How is it related to the Pisano period of the product of your two primes?
Take any two numbers A and B where A is a factor of B.
What are the Pisano periods of A and B?
What is the Pisano period of their product AB?
Is the Pisano period of A a factor of the Pisano period of B?
Look at the complete cycle for any modulus N. It always starts with 0, 1,... . Here is the complete cycle for 3:
mod 3: 0 1 1 2 0 2 2 1 - it has two zeros.
For 4 : 0 1 1 2 3 1 we have just one zero at the start
and for 5: 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 - we have four zeros.
Find a modulus N with some other number of zeros in its cycle.
The Relation of the Period Modulo m to the Rank of Apparition of m
in the Fibonacci Sequence John Vinson, Fibonacci Quarterly, vol 1 (1963), pages 37-45.
[With thanks to Robert Matthews of The Sunday Telegraph for suggesting this topic.]
Having looked at the end digits of Fibonacci numbers, we might ask
Are there any patterns in the initial digits of Fibonacci numbers?
What are the chances of a Fibonacci number beginning with "1", say? or "5"?
We might be forgiven for thinking that they probably are all the same - each digit
is equally likely to start a randomly chosen Fibonacci number. You only need to
look at the Table of the First 100 Fibonacci numbers or use
Fibonacci Calculator to see that this
is not so. Fibonacci numbers seem far more likely to start with "1" than any other
number. The next most popular digit is "2" and "9" is the least probable!
This law is called Benford's Law and appears in many tables of statistics.
Other examples are a table of populations of countries, or lengths of rivers.
About one-third of countries have a population size which begins with the digit "1" and very
few have a population size beginning with "9".
Initial digit frequencies of fib(i) for i from 1 to 100:
Digit: 1 2 3 4 5 6 7 8 9
Frequency: 30 18 13 9 8 6 5 7 4 100 values
Percent: 30 18 13 9 8 6 5 7 4
What are the frequencies for the first 1000 Fibonacci numbers or the first 10,000? Are they settling
down to fixed values (percentages)? Use the Fibonacci Calculator
to collect the statistics. According to Benford's Law, large numbers of items lead to the following
statistics for starting figures for the Fibonacci numbers as well as some natural phenomena
Digit:
1
2
3
4
5
6
7
8
9
Percentage:
30
18
13
10
8
7
6
5
5
You do the maths...
Look at a table of sizes of countries. How many countries areas begin with "1"? "2"? etc..
Use a table of population sizes (perhaps of cities in your country or of countries
in the world). It doesn't matter
if the figures are not the latest ones. Does Benford's Law apply to their initial digits?
Look at a table of sizes of lakes and find the frequencies of their initial digits.
Using the Fibonacci Calculator make a table
of the first digits of powers of 2. Do they follow Benford's Law? What about powers
of other numbers?
Some newspapers give lists of the prices of various stocks and shares, called "quotations".
Select a hundred or so of the quotations (or try the first hundred on the page) and make a table
of the distribution of the leading digits of the prices. Does it follow Benford's Law?
What other sets of statistics can you find which do show Benford's Law? What about the number
of the house where the people in your class live? What about the initial digit of their home
telephone number?
Generate some random numbers of your own and look at the leading digits.
You can buy 10-sided dice (bi-pyramids) or else you can cut out a
decagon (a 10-sided polygon with all sides the same length) from card and label the sides from 0 to 9.
Put a small stick through the centre (a used matchstick or a cocktail stick or a small
pencil or a ball-point pen) so that it can spin easily and falls on one of the sides at random.
(See the footnote about dice and spinners
on the "The Golden Geometry of the Solid Section or Phi in 3 dimensions" page, for picture
and more details.)
Are all digits equally likely or does this device show Benford's Law?
Use the random number generator on your calculator and make a table of leading-digit frequencies.
Such functions will often generate a "random" number between 0 and 1, although some calculators generate
a random value from 0 to the maximum size of number on the calculator. Or you can use the
random number generator in the Fibonacci Calculator
to both generate the values and count the initial digit frequencies, if you like.
Do the frequencies of leading digits of random values conform to Benford's Law?
Measure the height of everyone in your class to the nearest centimetre. Plot a graph of their
heights. Are all heights equally likely? Do their initial digits conform to Benford's Law?
Suppose you did this for everyone in your school. Would you expect the same distribution of
heights?
What about repeatedly tossing five coins all at once and counting the number of heads each time?
What if you did this for 10 coins, or 20?
What is the name of this distribution (the shape of the frequency graph)?
Random numbers are equally likely to begin with each of the digits 0 to 9. This applies to randomly
chosen real numbers or randomly chosen integers.
Randomly chosen real numbers
If you stick a pin at random on a ruler which is 10cm
long and it will fall in each of the 10 sections 0cm-1cm, 1cm-2cm, etc. with the same probability.
Also, if you look at the initial digits of the points chosen (so that the initial digit of 0.02cm is 2 even though
the point is in the 0-1cm section) then each of the 9 values from 1 to 9 is as likely as any other value.
Randomly chosen integers
This also applies if we choose random integers.
Take a pack of playing cards and remove the jokers, tens, jacks and
queens, leaving in all aces up to 9 and the kings. Each card will represent a different digit, with a king
representing zero. Shuffle the pack and put the first 4 cards in a row to represent a 4 digit integer.
Suppose we have King, Five, King, Nine. This will represent "0509" or the integer 509 whose first digit is 5.
The integer is as likely to begin with 0 (a king) as 1 (an ace) or 2 or any other digit up to 9.
But if our "integer" began with a king (0), then we look at the next "digit".
These have the same distribution as if we had chosen
to put down just 3 cards in a row instead of 4. The first digits all have the same probability again.
If our first two cards had been 0, then we look at the third digit, and the same applies again.
So if we ignore the integer 0, any randomly chosen (4 digit) integer begins with 1 to 9 with equal probability.
(This is not quite true of a row of 5 or more cards if we use an ordinary pack of cards - why?)
So the question is, why does this all-digits-equally-likely property
not apply to the first digits of each of the following:
the Fibonacci numbers,
the Lucas numbers,
populations of countries or towns
sizes of lakes
prices of shares on the Stock Exchange
Whether we measure the size of a country or
a lake in square kilometres or
square miles (or square anything), does not matter - Benford's Law will still apply.
So when is a number random? We often meant that we cannot predict the next value.
If we toss a coin, we can never predict if it will be Heads or Tails if we give it a
reasonably high flip in the air. Similarly, with throwing a dice - "1" is as likely as "6".
Physical methods such as tossing coins or throwing dice or picking numbered balls
from a rotating drum as in Lottery games are always unpredictable.
The answer is that the Fibonacci and Lucas Numbers are governed by a Power Law.
We have seen that Fib(i) is round(Phii/5) and Lucas(i) is
round(Phii). Dividing by sqrt(5) will merely adjust the scale - which does not matter.
Similarly, rounding will not affect the overall distribution of the digits in a large sample.
Basically, Fibonacci and Lucas numbers are powers of Phi. Many natural statistics are also governed
by a power law - the values are related to Bi for some base value B. Such data would seem to
include the sizes of lakes and populations of towns as well as non-natural data such as the collection of
prices of stocks and shares at any one time. In terms of natural phenomena (like lake sizes
or heights of mountains) the larger values are rare and smaller sizes are more common. So there are
very few large lakes, quite a few medium sized lakes and very many little lakes. We can see this with the
Fibonacci numbers too: there are 11 Fibonacci numbers in the range 1-100,
but only one in the next 3 ranges of 100 (101-200, 201-300,
301-400) and they get increasingly rarer for large ranges of size 100. The same is true for any other
size of range (1000 or 1000000 or whatever).
You do the maths...
Type a power expression in the Eval(i)= box, such as pow(1.2,i) and give a range of
i values from i=1 to i=100. Clicking the Initial digits button will print the leading digit
distribution.
Change 1.2 to any other value. Does Benford's Law apply here?
Using Eval(i)=randint(1,100000) with an i range from 1 to 1000 (so that 1000 separate
random integers are generated in the range 1 to 100000) shows that the leading digits are all equally likely.
Benford's Law for Fibonacci
and Lucas Numbers, L. C. Washington, The Fibonacci Quarterly
vol. 19, 1981, pages 175-177.
The original reference: The Law of Anomalous Numbers
F Benford, (1938) Proceedings of the American Philosophical Society vol 78,
pages 551-572.
The Math Forum's
archives of the History of Mathematics discussion group have
an email from
Ralph A. Raimi
(July 2000) about his research into Benford's Law. It seems that
Simon Newcomb had written about it much earlier, in 1881, in American Journal of Mathematics volume 4,
pages 39-40. The name Benford is, however, the one that is commonly used today for this law.
MathTrek by Ivars Peterson (author of The Mathematical Tourist and Islands of Truth)
the editor of Science News Online has produced this very good, short and readable
introduction to Benford's Law.
M Schroeder
Fractals, Chaos and Power Laws,
Freeman, 1991,
ISBN 0-7167-2357-3. This is an interesting book but some of the mathematics is at first year university
level (mathematics or physics degrees), unfortunately, and the rest will need sixth form or college level mathematics beyond age 16.
However, it is still good to browse through. It has only a passing reference to
Benford's Law: The Peculiar Distribution of the Leading Digit on page 116.
We found that every number is a factor of some Fibonacci number above
but it is also true that we can always find a Fibonacci number that begins with a given number as its initial
digits.
The first few Fibonacci numbers are 0,1,1,2,3,5,8. We have to go up to Fib(19)=4181 to find one beginning with 4 and
Fib(15)=641 for 6. The index numbers (ranks) of the Fibonacci numbers that begin with 1 up to 20 are:
Ross Honsberger (see the references at the end of this section) gives the proof that we can always find a power of 2
starting with any given number and, in fact, this works for any other base number as well as 2. The problem goes back to
a Hungarian Mathematical competition problem of 1928 (see references).
On another page we look at the Lucas numbers Lucas(n) = Fib(n-1) + Fib(n+1) and find that
Lucas(i) is Round(Phii) so the initial-digits-of-powers applies to the Lucas numbers also.
Is there a Fibonacci number that ends with any given number?
It seems we can start off, with the aid of a Calculator, and find Fibonacci numbers ending with all values from 1 to 99.
The list starts...
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Fib(i) ending with n
1
2
3
34
5
10946
377
8
89
610
17711
61922 0451666590 1352286753 8786329787 4269396512
13
704 9252476708 9125814114
6590346 2158763004 1982498215
57602 1322354247 5588620619 8685365216
24157817
196418
1140 5930102594 3970552219
154 8008755920
rank i
1
3
4
9
5
21
14
6
11
15
22
216
7
111
130
168
37
27
112
60
The list of ranks of these Fibonaccis-ending-with-n (their Fibonacci index numbers) is
1, 3, 4, 9, 5, 21, 14, ... A023183
Jason Earls comments that there seem to be none that end with
100, 102, 108, 110, 116, 118, ... or in fact any number beyond 99 that has a remainder of 4 or 6 when divided by 8.
Can you prove he is right?
We saw above that when we divide the Fibonacci numbers by a fixed divisor (modulus)
then we always get a cycle of remainders.
The length of this cycle is called the Pisano period of the modulus. For modulus 8, this cycle is of length 12:
i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Fib(i)
0
1
1
2
3
5
8
13
21
34
55
89
144
233
Fib(i) mod 8
0
1
1
2
3
5
0
5
5
2
7
1
0
1
We see no Fibonacci numbers leave a remainder 4 or 6 when divided by 8.
But 1000 is a multiple of 8 so the last 3 digits of any number N bigger than 1000 determine the remainder
when N itself is divided by 8.
So no Fibonacci number of 3 digits or more can end with a 3-digit number which has
a remainder of 4 or 6 when divided by 8.
By why do we get Fibonaccis ending with one or two digit numbers whose remainder is 4 or 6 mod 8?
The 1 or 2 digit numbers with a remainder of 4 or 6 mod 8 are:
4, 6, 12, 14, 20, 22, 28, 30, 36, 38, 44, 46, 52, 54, 60, 62, 68, 70, 76, 78, 84, 86, 92, 94
However, these can be the endings of larger numbers that are not equivalent to 4 or 6 mod 8,
such as a number ending 24 (ends in 4) or 946 (ends in 6).
So we see that are Fibonacci numbers longer than 2 digits whose one or two digit ending
is nevertheless one of the forbidden mod 8 remainders 4 or 6.
It happens that we can always find a Fibonacci number ending with any 1 or 2 numbers including those with a remainder or 4 or 6 mod 8:
1 or 2 digit ending
4
6
12
14
20
22
28
30
36
38
44
46
52
54
60
62
68
70
76
78
84
86
92
94
i
9
21
216
111
60
117
204
105
222
93
12
21
36
129
180
57
24
45
48
33
18
39
156
69
Fib(i) last 3 digits
34
946
512
114
920
322
528
730
936
738
144
946
352
954
760
162
368
170
976
578
584
986
792
994
Fib(i) mod 8
2
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
0
2
The Fibonacci Numbers in Pascal's Triangle
0
1
2
3
4
...
1
0
1
1 1
1
1
1
1 2 1
2
1
2
1
1 3 3 1
3
1
3
3
1
1 4 6 4 1
4
1
4
6
4
1
...
...
...
Each entry in the triangle on the left is the sum of the two numbers
above it.
If we re-align the table to look the one on the right then each number is the sum of the one above it and the one to the left of that one where a blank space can be
taken as "0". Note that each row starts and ends with "1".
Pascal's Triangle has lots of uses including
Calculating probabilities.
If you throw n coins randomly onto a table then
the chance of getting H heads among them is the entry in row N, col H
divided by 2n:
for instance, for 3 coins, n=3 so we use row 3:
3 heads: H=3 is found in 1 way (HHH)
2 heads: H=2 can be got in 3 ways (HHT, HTH and THH)
1 head: H=1 is also found in 3 possible ways (HTT, THT, TTH)
0 heads: H=0 (i.e. all Tails) is also possible in just 1 way: TTT
Finding terms in a Binomial expansion:
(a+b)n
EG. (a+b)3 = 1a3 + 3a2b
+ 3ab2 + 1b3
Can we find the Fibonacci Numbers in Pascal's Triangle? Yes! The answer lies in the diagonals in the triangle:
1
1
1
1
1
1
2
1
2
1
3
3
1
3
1
4
6
4
1
5
1
5
10
10
5
1
8
1
6
15
20
15
6
1
13
1
7
21
35
35
21
7
1
21
...
Why do the Diagonals sum to Fibonacci numbers?
It is easy to see that the diagonal sums really are the Fibonacci numbers if we
remember that each number in Pascal's triangle is the sum of two numbers in the
row above it (blank spaces count as zero),
so that 6 here is the sum of the two 3's on the row above.
The numbers in any diagonal row are therefore formed from adding numbers in the
previous two diagonal rows as we see here where all the blank spaces are zeroes
and where we have introduced an extra column of zeros which we will use later:
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
1
5
10
10
5
1
1
6
15
20
15
6
1
The green diagonal sums to 5;
the blue diagonal sums to 8;
the red diagonal sums to 13
Each red number is the sum of a blue
and a green number on the row above.
Notice that the GREEN numbers are on one diagonal and the
BLUE ones on the next. The sum of all the green numbers
is 5 and all the blue numbers add up to 8.
Because all the numbers in Pascal's Triangle are made the same way -
by adding the two numbers above
and to the left on the row above,
then we can see that each red number is just the
sum of a green number and a blue number and we use up all the blue and green numbers
to make all the red ones.
The sum of all the red numbers is
therefore the same as the sum of all the blues and all the greens: 5+8=13!
The general
principle that we have just illustrated is:
The sum
of the numbers on one diagonal is the sum of the numbers on the previous
two diagonals.
If we let D(i) stand for the sum of the numbers on the Diagonal that starts with
one of the extra zeros at the beginning of row i, then
D(0)=0 and D(1)=1
are the two initial diagonals shown in the table above. The green diagonal
sum is
D(5)=5 (since its extra initial zero is in row 5) and the blue diagonal sum is D(6)
which is 8. Our red diagonal is D(7) = 13 = D(6)+D(5).
We also have shown that this is always true: one diagonals sum id the sum of the
previous two diagonal sums, or, in terms of our D series of numbers:
D(i) = D(i-1) + D(i-2)
But...
D(0) = 1
D(1) = 1
D(i) = D(i-1) + D(i-2)
is
exactly the definition of the Fibonacci numbers! So D(i) is just F(i) and
the sums of the diagonals in Pascal's Triangle are the Fibonacci numbers!
Another arrangement of Pascal's Triangle
By drawing Pascal's Triangle with all the rows moved over by 1 place, we have a clearer
arrangement which shows the Fibonacci numbers as sums of columns:
1
2
3
4
5
6
7
8
9
10
1
.
.
.
.
.
.
.
.
.
.
1
1
.
.
.
.
.
.
.
.
.
1
2
1
.
.
.
.
.
.
.
.
1
3
3
1
.
.
.
.
.
.
.
1
4
6
4
1
.
.
.
.
.
.
1
5
10
10
5
.
.
.
.
.
.
1
6
15
20
.
.
.
.
.
.
.
1
7
21
.
.
.
.
.
.
.
.
1
8
.
.
.
.
.
.
.
.
.
1
1
1
2
3
5
8
13
21
34
55
This table can be explained by referring to one of the
(Easier) Fibonacci Puzzles - the one about
Fibonacci for a Change. It asks how many ways you can pay n pence (in the UK)
using only 1 pence and 2 pence coins. The order of the coins matters, so that 1p+2p will pay for a 3p item
and 2p+1p is counted as a different answer.
[We now have a new two pound coin that
is increasing in circulation too!]
Here are the answers for paying up to 5p using only 1p and 2p coins:
Let's look at this another way - arranging our answers according to the number of
1p and 2p coins we use. Columns will represent all the ways of paying the amount at the head
of the column, as before, but now the rows represent the number of coins in the solutions:
cost:
1p
2p
3p
4p
5p
1 coin:
1p
2p
2 coins:
1p+1p
1p+2p 2p+1p
2p+2p
3 coins:
1p+1p+1p
1p+1p+2p 1p+2p+1p 2p+1p+1p
1p+2p+2p 2p+1p+2p 2p+2p+1p
4 coins:
1p+1p+1p+1p
2p+1p+1p+1p
1p+1p+1p+2p 1p+1p+2p+1p 1p+2p+1p+1p
5 coins:
1p+1p+1p+1p+1p
If you count the number of solutions in each box, it will be exactly the form of Pascal's triangle that
we showed above!
The mathematics is in this formula:
where the big brackets with two numbers vertically inside them
are a special mathematical notation for the entry in Pascal's triangle
on row n-k-1 and column k
Here's another explanation of how the Pascal triangle numbers sum to give the
Fibonacci numbers, this time explained in terms of our original rabbit problem.
Let's return to Fibonacci's rabbit problem and look at it another way. We
shall be returning to it several more times yet in these pages - and each time
we will discover something different!
We shall make a family tree of the rabbits but this time we shall be interested
only in the females and ignore any males in the population. If you like,
in the
diagram of the rabbit pairs shown here, assume that the rabbit on the left
of each pair is male (say)
and so the other is female. Now ignore the rabbit on the left in each pair!
We will assume that
each mating produces exactly one female and perhaps some males too but we only show
the females in the diagram on the left.
Also in the diagram on the left we see that each individual rabbit appears several times.
For instance, the original brown female was mated with a while male and, since they never
die, they both appear once on every line.
Now, in our
new family tree diagram, each female rabbit will appear only once.
As more rabbits
are born, so the Family tree grows adding a new entry for each newly born female.
As in
an ordinary human family tree, we shall show parents above a line of all their children.
Here is a fictitious human family tree with the names of the relatives shown for a person
marked as ME:
The diagram shows that:
Grandpa Abel and Grandma Mabel are the parents of my Dad;
Grandma Freda and Grandpa Fred are the parents of my Mum.
Bob is my Dad's brother
my Mum has two sisters, my aunts Hayley and Jane.
Aunt Hayley became Hayley Weather when she married Clement Weather.
They have two children, my cousins Sonny Weather and Gale Weather.
Gale married Gustof Wind and so is now Gale Wind.
My brother John and his wife Joan have two children, my nephew Dan and my niece Pam.
In this family tree of human relationships, the = joins people who
are parents or signifies a marriage.
In our rabbit's family tree, rabbits don't marry of course, so we just have the
vertical and horizontal lines:
The vertical line |
points from a mother (above) to the oldest daughter (below);
the horizontal line -
is drawn between sisters from the oldest on the left down to the youngest on the right;
the small letter r
represents a young female ( a little rabbit) and
the large letter R
shows a mature female (a big Rabbit)
who can and does mate every month, producing one new
daughter each time.
As in Fibonacci's
original problem (in its variant form that makes it a bit more realistic) we assume none die
and that each month every mature female rabbit R always produces exactly
one female rabbit r (we ignore males) each month.
So each month:
each r will change to R (each matures after one month)
each R produces a new baby rabbit and so adds another r at the end of the line below
which are its direct descendants or children), that is produce a new baby rabbit each month
Here is the Rabbit Family tree as if grows month by month for the first
9 months and 5 generations:
KEY |:mother above with (first) daughter below
__:joins sisters R:mother (produces a new female each month)
r:new female
Month:
1 R
|
2 R_______________R_________R_____R___R_R_r
| | | | |
3 R_____R___R_R_r R___R_R_r R_R_r R_r r
| | | | | |
4 R_R_r R_r r R_r r r
|
5 r
21 R + 13 r = 34
1 R
|
2 R_______________R_________R_____R___R_r
| | | |
3 R_____R___R_r R___R_r R_r r
| | |
4 R_r r r
13 R + 8 r = 21
1 R
|
2 R_______________R_________R_____R___r
| | |
3 R_____R___r R___r r
|
4 r
8 R + 5 r = 13
1 R
|
2 R_______________R_________R_____r
| |
3 R_____r r
5 R + 3 r = 8
1 R
|
2 R_______________R_________r
| ^ the original rabbit produces another daughter
3 r ^ becomes mature^the first daughter produces her first offspring, the first of generation 3 (grand-children)
3 R + 2 r = 5
1 R
|
2 R_______________r
^ the original rabbit produces another daughter
^the female born in month 3 becomes mature
2 R + 1 r = 3
1 R
|
2 r the first rabbit produces a daughter (second generation)
1 R + 1 r = 2
1 R
The female (r of month 1) becomes mature (R) and mates
1 R + 0 r = 1
1 r
^Initially there is one immature rabbit (generation 1)
0 R + 1 r = 1
The Family tree is shown for the first 9 months as more females are added to it. We
can see that our original female becomes a great-grandmother in month 7 when a fourth line
is added to the Family tree diagram - a fourth generation!
Have you spotted the Pascal's triangle numbers in the Rabbit's Family Tree?
The numbers of rabbits in each generation, that is, along each level (line) of the tree,
are the Pascal's triangle numbers that add up to give each Fibonacci number -
the total number of (female) rabbits in the Tree. In month n there are a total
of F(n) rabbits, a number
made up from the entry in row (n-k) and column (k-1) of Pascal's triangle for each of the
levels (generations) k from 1 to n. In other words, we are looking at this formula and
explaining it in terms of generations, the original rabbit forming generation 1 and her
daughters being generation 2 and so on:
Fib(n)=
n
k=1
(
n–k
k–1
)
Remember that the rows and columns of Pascal's triangle in this formula
begin at 0!
For example, in month 8, there are 4 levels and the number on
each level is:
1 R
|
2 R_______________R_________R_____R___R_r
| | | |
3 R_____R___R_r R___R_r R_r r
| | |
4 R_r r r
Generation 1: 1 rabbit which is Pascal's triangle row 7 (8-1), column 0 (1-1)
Generation 2: 6 rabbits which is Pascal's triangle row 6 (8-2), column 1 (2-1)
Generation 3: 10 rabbits which is Pascal's triangle row 5 (8-3), column 2 (3-1)
Generation 4: 4 rabbits which is Pascal's triangle row 4 (8-4), column 3 (4-1)
When k is bigger than 4, the column number exceeds the row number in Pascal's
Triangle and all those entries are 0.
1+6+10+4 is F(8)=21
col:
0
1
2
3
4
5
6
7
8
...
r o w
0
1
0
0
0
0
0
0
0
0
...
1
1
1
0
0
0
0
0
0
0
...
2
1
2
1
0
0
0
0
0
0
...
3
1
3
3
1
0
0
0
0
0
...
4
1
4
6
4
1
0
0
0
0
...
5
1
5
10
10
5
1
0
0
0
...
6
1
6
15
20
15
6
1
0
0
...
7
1
7
21
35
35
21
7
1
0
...
8
1
8
28
56
70
56
28
8
1
...
...
...
The general pattern for month n and level (generation) k is
Level k: is Pascal's triangle row n-k and column k-1
For month n we sum all the generations as k goes from 1 to n (but half of these will be zeros).
There is a very nice
Maths is Fun simulation of a quincunx
showing each ball bouncing as it falls.
You do the maths...
Make a diagram of your own family tree. How far back can you go? You will probably
have to ask your relatives to fill in the parts of the tree that you don't know, so
take your tree with you on family visits and keep extending it as you learn about
your ancestors!
Start again and draw the Female Rabbit Family tree, extending it month by month.
Don't distinguish between
r and R on the tree, but draw the newly born rabbits using a new colour for
each month or, instead of using lots of colours, you could just put a number
by each rabbit showing in which month it was born.
If you tossed a coin 10 times, how many possible sequences of Heads and Tails could
there be in total (use Pascal's Triangle extending it to the row numbered 10)?
In how many of these are there 5 heads (and so 5 tails)? What is the probability of
tossing 10 coins and getting exactly 5 heads therefore - it is not 0·5!
Draw up a table for each even number of coins from 2 to 10 and show the
probability of getting exactly half heads and half tails for each case. What is happening
to the probability as the number of coins gets larger?
Draw a histogram of the 10th row of Pascal's triangle, that is,
a bar chart, where each column on the row numbered 10 is shown as a bar whose height
is the Pascal's triangle number. Try it again for tow 20 if you can (or use
a Spreadsheet on your computer). The shape that you get as the row increases is
called a Bell curve since it looks like a bell cut in half. It has many
uses in Statistics and is a very important shape.
Make a Galton Quincunx.
This is a device with lots of nails put in a regular
hexagon arrangement. Its name derives from the Latin word quincunx
for the X-like shape of the spots on the 5-face of a dice:
Hopper for balls
balls fall onto nails with an
equal chance of bouncing to
left or right each time
balls collect in hoppers
The whole board is tilted forward slightly so that the top is raised off the table
a little. When
small balls are poured onto the network of nails at the top, they fall
through, bouncing either to the right
or to the left and so hit another nail on the row below. Eventually they fall
off the bottom row of nails and are caught in containers.
If you have a lot of nails and a lot
of little balls (good sources for these are
small steel ball-bearings
from a bicycle shop or ping-pong balls for a large version
or even dried peas or other cheap round seeds from the supermarket)
then they end up forming a shape in the containers that is
very much like the Bell curve of the
previous exploration.
You will need to space the nails so they are as far apart as about
one and a half times the width of the balls you are using.
Let's see how the curve of the last two explorations, the Bell curve
might actually occur
in some real data sets.
Measure the height of each person in your class and plot a graph
similar to the containers above, labelled with heights to the nearest
centimetre, each container containing one ball for each person with that height.
What shape do you get? Try adding in the results from other classes to get one big graph.
This makes a good practical demonstration for a Science Fair or Parents' Exhibition
or Open Day
at your school or college.
Measure the height of each person who passes your display and
"add a ball" to the container which represents their height. What shape do you get at the
end of the day?
What else could you measure?
The weight of each person to the nearest pound or nearest 500 grams;
their age last birthday;
but remember some people do not like disclosing their age or knowing too accurately
their own weight!
house or apartment number (what range of values should you allow for? In the USA
this might be up to several thousands!)
the last 3 digits of their telephone number;
or try these data sets using coins and dice:
the total number when you add the spots after throwing 5 dice at once;
the number of heads when you toss 20 coins at once.
Do all of these give the Bell curve
for large samples?
If not, why do you think some do and some don't?
Can you decide
beforehand which will give the Bell curve and which won't? If a distribution is not a Bell curve,
what shape do you think it will be? How can mathematics help?
Write out the first few powers of 11. Do they remind you of Pascal's
triangle? Why? Why does the
Pascal's triangle pattern break down after the first few powers?
(Hint: consider (a+b)m where a=10 and b=1).
To finish, let's return to a human family tree. Suppose that the probability of
each child being male is exactly 0.5 so that exactly half of all new babies will be male and half
female.
If a couple have 2 children, what are the four possible sequences
of children they can have?
What is it if they have 3 children?
In what proportion of the couples that have 3 children will all 3 children
be girls?
Suppose a couple have
4 children, what is the probability now that all 4 will be girls?
We can align these terms up so that all the same powers of x are in the same column (as we would do when doing
ordinary decimal arithmetic on numbers) as follows:
P(x) =
F(0)x
+ F(1)x2
+ F(2)x3 + F(3)x4 + ...
+F(n-1)xn + ...
x P(x) =
F(0)x2
+ F(1)x3 + F(2)x4 + ...
+F(n-2)xn + ...
x2 P(x) =
F(0)x3 + F(1)x4 + ...
+F(n-3)xn + ...
We have done this so that each Fibonacci number in P(x) is aligned with the two previous Fibonacci
numbers. Since the sum of the two previous numbers always equals the next in the Fibonacci series,
then, when we take them away, the result will be zero - the terms will vanish!
So, if we take away the last two expressions (for x P(x) and x2 P(x))
from the first equation for P(x),
the right-hand side will simplify since all but the first few terms vanish, as shown here:
P(x)=
F(0)x +
F(1)x2 +
F(2)x3 + F(3)x4 + ... +F(n-1)xn + ...
x P(x) =
F(0)x2 +
F(1)x3 + F(2)x4 + ... +F(n-2)xn + ...
x2 P(x) =
F(0)x3 + F(1)x4 + ... +F(n-3)xn + ...
(1 – x – x2) P(x) =
F(0)x +
(F(1)–F(0))x2 +
(F(2)–F(1)–F(0))x3+...
Apart from the first two terms, the general term, which is just
the coefficient of xn, becomes F(n)–F(n–1)–F(n–2) and,
since F(n) = F(n–1) + F(n–2) all but the first two terms become zero which is why we wrote down
x P(x) and x2 P(x):
(1 – x – x2) P(x)
=
x2
P(x)
=
x2
1 – x – x2
=
1
x–2 – x–1 – 1
The polynomial P(x) which has the Fibonacci numbers as the coefficients of
its powers of x is called a generating function for the Fibonacci numbers.
Finding such a polynomial for other series of numbers is an important part of modern mathematics and has many applications. Abraham De Moivre (1667-1754) is the person who first wrote about this technique in his book on Probability
The Doctrine of Chances: Or, A Method of Calculating the Probability of Events in Play
in 1718.
He used it exactly as we have done here for the Fibonacci numbers!
Fibonacci decimals
So now our fraction is just P(1/10), and the right hand side tells us its exact value:
1 / (100-10-1) = 1/89 = 0·0112358...
From our expression for P(x) we can also deduce the following:
The decimal expansions of fractions here in the Calculator
are produced to any number of decimal places, unlike an ordinary calculator which only gives perhaps a maximum of 15 decimal places.
Expand these fractions and say how they are related to the Fibonacci numbers:
10
89
the Fibonacci numbers starting at 1,1,...
2
995999
every third Fibonacci number starting at 0,(1,1),2,(3,5),8,... with 3 digits per number
999
995999
every third Fibonacci number starting at (0,)1,(1,2),3,(5,8),13,... with 3 digits per number
1001
995999
every third Fibonacci number starting at (0,1),1,(2,3),5,(8,13),21,... with 3 digits per number
The Decimal Expansion of 1/89
and related Results, Fibonacci Quarterly, Vol 19, (1981), pages 53-55.
Calvin Long solves the general problem for all Fibonacci-type
sequences i.e. G(0)=c, G(1)=d are the two starting terms and G(i) = a G(i-1) + b G(i-1) defines
all other values for integers a and b. For our "ordinary" Fibonacci sequence,
a=b=1 and c=d=1. He gives the exact fractions for any base B (here B=10 for decimal fractions)
and gives conditions when the fraction exists (i.e. when the series does not get too large too
quickly so that we do have a genuine fraction).
A Complete Characterisation of the Decimal Fractions that can be
Represented as SUM(10-k(i+1)F(ai)) where F(ai) is the aith Fibonacci number
Richard H Hudson and C F Winans, Fibonacci Quarterly, 1981, Vol 19, pp 414 - 421.
This article examines all the decimal fractions where the terms
are F(a), F(2a), F(3a)
taken k digits at a time in the decimal fraction.
A Primer For the Fibonacci Numbers: Part VI, V E Hoggatt Jr, D A Lind
in Fibonacci Quarterly, vol 5 (1967) pages 445 - 460
is a nice introduction to Generating Functions (a polynomial in x where
the coefficients of the powers of x are the members of a particular series).
The whole collection of articles is now available in book form by mail order from
The Fibonacci Association.
It is
readable and not too technical. There is also a list of formulae for all kinds
of generating functions, which, if we substitute a power of 10 for x, will give a
large collection of fractions whose decimal expansion is , for example:
the Lucas Numbers (see this page at this site)
e.g. 1999/998999
the squares of the Fibonacci numbers e.g.
999000/997998001
the product of two neighbouring Fibonacci numbers e.g. 1000/997998001
the cubes of the Fibonacci numbers e.g. 997999000/996994003001
the product of three neighbouring Fibonacci numbers e.g. 2000000000/996994003001
every kth Fibonacci number e.g. 1000/997001 or 999000/997001
etc.
Scott's Fibonacci Scrapbook, Allan Scott in Fibonacci Quarterly
vol 6 number 2, (April 1968), page 176
is a follow-up article to the one above, extending the generating functions to
Lucas cubes and Fibonacci fourth and fifth powers.
Note there are several corrections to these equations
on page 70 of vol 6 number 3 (June 1968).
Here is a little trick you can perform on friends which seems to show that you have amazing
mathematical powers. We explain how it works after showing you the trick.
A Lightning Calculation
Here is Alice performing the trick on Bill:
Alice: Choose any two numbers you like, Bill, but not too big as you're going to
have to do some adding yourself. Write them as if you are going to add them up
and I'll, of course, be looking the other way!
Bill: OK, I've done that.
Bill chooses 16 and 21 and writes them one under the other:
16
21
Alice: Now add the first to the second and write the sum underneath to make the
third entry in the column.
Bill: I don't think I'll need my calculator just yet.... Ok, I've done that.
Bill writes down 37 (=16+21) under the other two:
16
21
37
Alice: Right, now add up the second and your new number and again write their
sum underneath. Keep on doing this, adding the number you have just written to
the number before it and putting
the new sum underneath. Stop when you have 10 numbers written down and draw a line under the tenth.
There is a sound of lots of buttons being tapped on Bill's calculator!
Bill: OK, the ten numbers are ready.
Bills column now looks like this:
16
21
37
58
95
153
248
401
649
1050
Alice: Now I'll turn round and look at your numbers and write the sum of all
ten numbers straight away!
She turns round and almost immediately writes underneath: 2728.
Bill taps away again on his calculator and is amazed that Alice got it right in so
short a time [gasp!]
So how did Alice do it?
The sum of all ten numbers is just
eleven times the fourth number from the bottom. Also, Alice knows the quick method
of multiplying a number by eleven. The fourth number from the bottom is 248,
and there is the quick and easy method of multiplying numbers by 11
that you can easily do in your head:
Starting at the right, just copy the last digit of the number as the
last digit of your product.
Here the last digit of 248 is 8
so the product also ends with 8 which Alice writes down:
... 248
401
649
1050
8
Now, continuing in 248, keep adding up from the right each number and its neighbour,
in pairs, writing down their sum as you go.
If ever you get a sum bigger than 10, then write down the units digit of the sum and
remember to carry anything over into your next pair to add.
Here the pairs of 248 are (from the right) 4+8 and then 2+4.
So, next to the 8 Alice thinks
"4+8=12" so she writes 2 and remembers there is an
extra one to add on to the next pair:
... 248
401
649
1050
28
Then 2+4 is 6, adding the one carried makes 7, so she
writes 7 on the left of those digits already written down:
... 248
401
649
1050
728
Finally copy down the left hand digit (plus any carry).
Alice sees that the left digit is 2
which, because there is nothing being carried from the previous
pair, becomes the left-hand digit of the sum.
The final sum is therefore 2728 = 11 x 248 .
... 248
401
649
1050
2728
Why does it work?
You can see how it works using algebra and by starting with A and B as the two numbers that Bill chooses.
What does he write next? Just A+B in algebraic form.
The next sum is B added to A+B which is A+2B.
The other numbers in the column are 2A+3B, 3A+5B, ... up to 21A+34B.
A
B
A + B
A + 2B
2A + 3B
3A + 5B
5A + 8B
8A +13B
13A +21B
21A +34B
--------
55A +88B
If you add these up you find the total sum of all ten is 55A+88B.
Now look at the fourth number up from the bottom. What is it?
How is it related to the final sum of 55A+88B?
So the trick works by a special property of adding up exactly ten numbers
from a Fibonacci-like sequence and will work for any two starting values A and B!
Perhaps you noticed that the multiples of A and B were the Fibonacci numbers?
This is part of a more
general pattern which is the first investigation of several to spot new patterns in
the Fibonacci sequence in the next section.
On a Fibonacci Arithmetical Trick C T Long, Fibonacci Quarterly
vol 23 (1985), pages 221-231. This article introduces the above trick and generalises it.
Practice here with "Bill"
Here is your very own "Bill" to practice on.
Click on the "Show Bill's list"
button and he will think of two numbers and show you his
list.
Enter your answer in the Sum: box
Click on Am I right? to see if you got it right!
Click on Show Bill's list as often as you like to get a new list.
Sum:
A Fibonacci GeneralisationBrother Alfred Brousseau, Fibonacci Quarterly
vol 5 (1967), pages 171-174. This article introduces the above trick and generalises it to sums of more numbers.
On a Fibonacci Arithmetical Trick C T Long, Fibonacci Quarterly
vol 23 (1985), pages 221-231. Another generalisation.
Another Number Pattern
Dave Wood has found another number pattern that we can prove using the same method.
He notices that
f(10)-f(5) is 55 - 5 which is 50 or 5 tens and 0;
f(11)-f(6) is 89 - 8 which is 81 or 8 tens and 1;
f(12)-f(7) is 144 - 13 which is 131 or 13 tens and 1.
It looks like the differences seem to be 'copying' the Fibonacci series in the tens and in the
units columns.
If we continue the investigation we have:
f(13)-f(8) is 233 - 21 which is 212 or 21 tens and 2;
f(14)-f(9) is 377 - 34 which is 343 or 34 tens and 3;
f(15)-f(10) is 610 - 55 which is 555 or 55 tens and 5;
f(16)-f(11) is 987 - 89 which is 898 or 89 tens and 8;
f(17)-f(12) is 1597 - 144 which is 1453 or 144 tens and 13;
From this point on, we have to borrow a ten in order to make the 'units' have the 2 digits needed
for the next Fibonacci number. Later we shall have to 'borrow' more, but the pattern
still seems to hold.
In words we have:
For any Fibonacci number:
if we take away the Fibonacci number 5 before it the result is
ten times the number we took away PLUS the Fibonacci number ten before it
In mathematical terms, we can write this as:
Fib(n) - Fib(n-5) = 10 Fib(n-5) + Fib(n-10)
A Proof
That the pattern always holds is found by extending the table we used
in the Why does it work section of the Number Trick above:
A
B
A + B
A + 2B
2A + 3B
3A + 5B
5A + 8B
8A +13B
13A +21B
21A +34B
34A +55B
We can always write any Fibonacci number Fib(n) as 34A+55B because, since the Fibonacci series
extends backwards infinitely far, we just pick A and B as the two numbers that are 10
and 9 places before the one we want.
Now let's look at that last line: 34A +55B.
It is almost 11 times the number 5 rows before it:
11 x (3A+5B) = 33A+55B,
and it is equal to it if we add on an extra A, i.e. the number ten
rows before the last one:
34A + 55B = 11 (3A+5B) + A
Putting this in terms of the Fibonacci numbers, where the 34A+55B is F(n) and 3A+5B is
"the Fibonacci number 5 before it", or Fib(n-5) and A is "the Fibonacci number 10 before
it" or Fib(n-10), we have:
34A + 55B = 11 (3A+5B) + A
or
Fib(n) = 11 Fib(n-5) + Fib(n-10)
We rearrange this now by taking Fib(n-5) from both sides and we have:
A Pythagorean Triangle
is a right-angled triangle with sides which are whole numbers.
In any right-angled triangle with sides s and t and longest side (hypotenuse) h,
the Pythagoras Theorem applies:
s2 + t2 = h2
However, for a Pythagorean triangle, we also want the sides to be integers (whole numbers)
too.
A common example is a triangle with sides s=3, t=4 and h=5:
We can check Pythagoras theorem:
s2 + t2
= 32 + 42
= 9 + 16
= 25 = 52 = h2
Here is a list of some of the smaller Pythagorean Triangles:
You will see that some are just magnifications of smaller ones where all
the sides have been doubled, or trebled for example. The others are
"new" and are usually called primitive Pythagorean triangles.
Any Pythagorean triangle is either primitive or a multiple of a primitive and this
is shown in the table above.
Primitive Pythagorean triangles are a bit like prime numbers in that
every Pythagorean triangle is either primitive (no number is `the 3 sides do not have a common factor)
or is a multiple of a primitive Pythagorean triangle.
There is an easy way to generate Pythagorean triangles using 4 Fibonacci numbers.
Take, for example, the 4 Fibonacci numbers:
1, 2, 3, 5
Let's call the first two a and b. Since they are from the Fibonacci series,
the next is the sum of the previous two: a+b and the following one is b+(a+b) or a+2b:-
a
b
a+b
a+2b
1
2
3
5
You can now make a Pythagorean triangle as follows:
Multiply the two middle or inner numbers (here 2 and 3 giving 6);
Double the result (here twice 6 gives 12). This is one side, s, of the
Pythagorean Triangle.
Multiply together the two outer numbers (here 1 and 5 giving 5).
This is the second side, t, of the Pythagorean triangle.
The third side, the longest, is found by adding together the squares
of the inner two numbers
(here 22=4 and 32=9 and their sum is 4+9=13).
This is the third side, h, of the Pythagorean triangle.
We have generated the 12, 5,13 Pythagorean triangle, or, putting the sides in order,
the 5, 12, 13 triangle this time.
Try it with 2, 3, 5 and 8 and check that you get the Pythagorean triangle: 30, 16, 34.
Is this one primitive?
In fact, this process works for any two numbers a and b, not just Fibonacci numbers.
The third and fourth numbers are found using the Fibonacci rule: add the latest
two values to get the next.
Four such numbers are part of a generalised Fibonacci series which we could
continue for as long as we liked, just as we did for the (real) Fibonacci series.
All primitive Pythagorean triangles can be generated in this way by choosing suitable
starting numbers a and b but not all non-primitive ones are!
For the reason for this and lots more on Pythagorean triangles see
my Pythagorean Triangles page.
Try the Fibonacci method for yourself and check with this Calculator:
Pythagorean Triples from Fibonacci-type Series Calculator
Connections in Mathematics: An Introduction to Fibonacci via Pythagoras
E A Marchisotto in Fibonacci Quarterly, vol 31, 1993, pages 21 - 27.
This article explores many ways of introducing the Fibonacci numbers in class starting from
the Pythagorean triples, with an extensive Appendix of references useful for the teacher
and comparing different approaches. Highly recommended!
Pythagorean Triangles from the Fibonacci Series C W Raine in
Scripta Mathematica vol 14 (1948) page 164.
Fibonacci Numbers as the sides of Pythagorean Triangles
Can we form a triangle (not necessarily right-angled) from three distinct Fibonacci numbers?
No, because of the following condition that must be true for any and all triangles:
in any triangle the longest side must be shorter than the sum of the other two sides
This is called the Triangle Inequality.
Since three consecutive Fibonacci numbers
already have the third number equal to the sum of the other two, then the Triangle Inequality
fails. Or, if you prefer, the two shorter sides collapse onto the third to form a
straight line when you try to construct a triangle from
these numbers.
If the smallest side is smaller, that makes it worse, as it does
if the longer side gets longer!
So we have
No triangle has sides which are three distinct Fibonacci numbers
So can we have a triangle with three Fibonacci numbers as sides,
but with two sides equal?
Yes: 3,3,5 will do. The longest side, 5, is now less than the sum of the other two, 3+3.
But this triangle is not right-angled:
32 + 32 is 18 whereas 52 is 25.
No Pythagorean triangle has two equal sides. If we ask for just two sides which are Fibonacci
numbers, the third being any whole number, then
there are at least two Pythagorean triangles with Fibonacci numbers on
two sides:
3, 4, 5 and
5, 12, 13
It is still an unsolved problem as to whether there are any more right-angled
(Pythagorean) triangles with just two Fibonacci numbers as sides.
Can we have any other Pythagorean triangles with a Fibonacci number
as the hypotenuse (the longest side)? Yes!
We can make every odd-indexed Fibonacci number the hypotenuse of a Pythagorean triangle
using the technique of the section above.
We take 4 consecutive Fibonacci numbers:
F(n – 1) F(n) F(n + 1) F(n + 2)
and get the two sides of a Pythagorean Triangle:
2 F(n)F(n + 1) and F(n – 1)F(n + 2)
The hypotenuse is the sum of the squares of the middle two numbers:
F(n)2 + F(n + 1)2 and Lucas showed in 1876 that this is just
F(2n + 1).
So we have the following Pythagorean Triangle with an odd-indexed Fibonacci number as hypotenuse:
2F(n)F(n + 1) ; F(n – 1)F(n + 2) ; F(2n + 1)
Here are some examples:
n
2
3
4
5
...
2F(n)F(n + 1)
4
12
30
80
...
F(n – 1)F(n + 2)
3
5
16
39
...
F(2n + 1)
5
13
34
89
...
Is this the only series of Pythagorean Triangles with hypotenuses that are
Fibonacci numbers?
Pythagorean Triples A F Horadam Fibonacci Quarterly vol 20 (1982) pages 121-122.
Square Fibonacci Numbers
Let's have a further look at that formula of Lucas from 1876:
F(n)2 + F( n + 1)2 = F(2n + 1)
We can make this into a Pythagorean triangle whenever F(2n+1) is a square number.
So we now have the question
Which Fibonacci numbers are square numbers?
We only have to look at the first few Fibonacci numbers to spot these square numbers:
F(0)=0=02; F(1)=F(2)=1=12; F(12)=144=122
But a longer look does not reveal any more squares among the Fibonacci's. Are these the
only Fibonacci squares? Yes, as was proved by Cohn in the article below.
Therefore...
Two consecutive Fibonacci numbers cannot
be the sides of a Pythagorean Triangle.
Square Fibonacci Numbers Etc. J H E Cohn in Fibonacci Quarterly vol 2 (1964)
pages 109-113
Other right-angled triangles and the Fibonacci Numbers
Even if we don't insist that all three sides of a right-angled triangle are integers, Fibonacci numbers still have
some interesting applications.
For instance, if we choose
two consecutive Fibonacci numbers as the sides next to the right angle,
then the third side squared is also a Fibonacci number.
For instance, if the sides are 3 and 5, by Pythagoras' Theorem we have that the hypotenuse, h, is given by:
32 + 52 = h2
and 9 + 25 = 34, another Fibonacci number. So h is √34.
If we look at the indices of the Fibonacci numbers, we can directly predict which Fibonacci number will be the
square of the hypotenuse.
For our example here, F(4)=3 and
F(5)=5 and the hypotenuse-squared is 34=F(9).
9, the index
of the h2 Fibonacci number is the sum of the other two indices, 4 and
5. This is also true in general, provided the two Fibonacci sides are consecutive Fibonacci
numbers, say F(n) and F(n+1):
F(n)2 + F(n + 1)2 = F(2 n + 1) .......... Lucas (1876)
This rule was known (and proved) by E Lucas in 1876.
I am grateful to Richard Van De Plasch for pointing out this application of Lucas's formula to right-angled
triangles.
You do the maths...
There are just 3 other right-angled triangles with Fibonacci sides that are not consecutive
Fibonacci numbers and also with a hypotenuse whose square is a Fibonacci number. What are they? (Hint: the sides and the hypotenuse-squared are all single digit numbers!)
With sides 1 and 3, a right-angled triangle has hypotenuse √10 and, although 10 is not a Fibonacci number
it is twice a Fibonacci number.
This is also true of 1, 5, √26 because 26 is twice 13 and F(7) = 13
and 2, 8, √68 and 68 is twice 34 which is F(9).
Are there any other such triangles? If so, is there a general rule?
Try replacing the factor 2 in the previous investigation by another number.
What new rules can you find?
The investigations above will lead you to Catalan's Identity of 1879 which is on
this site's Formula page. We can rearrange it as follows:
For the investigations above we use a special case where r is an odd number (2k + 1) more than n;
i.e. (n – r) is (2k + 1) for any integer k.
This means that:
the –(–1)n – r on the left-hand side becomes just a + sign since n – r is odd;
the factor F(n – r) on the right is just F(2k + 1) which is why the factors
above: 2, 5, 13, 34,... are alternate Fibonacci numbers - the ones with an odd index.
the Fibonacci number F(n + r) in the hypotenuse has an index (n + r)
which is the sum of the indices of
the Fibonacci numbers on the other two sides of the triangle (n and r).
Let's look again at the Fibonacci squares and spiral
that we saw in the Fibonacci Spiral section of
the Fibonacci in Nature page.
Wherever we stop, we will always get a rectangle, since the next square to add is
determined by the longest edge on the current rectangle. Also,
those
longest edges are just the sum of the latest two sides-of-squares
to be added. Since we start with squares of sides 1 and 1, this tells us why the
squares sides are the Fibonacci numbers (the next is the sum of the previous 2).
Also, we see that each rectangle is a jigsaw puzzle made up of all the earlier squares
to form a rectangle. All the squares and all the rectangles
have sides which are Fibonacci numbers in length. What is the mathematical
relationship that is shown by this pattern of squares and rectangles? We express
each rectangle's area as a sum of its component square areas:
The diagram shows that
12 + 12 + 22 + 32 + 52 + 82 + 132 = 13×21
and also, the smaller rectangles show:
12 + 12
=
1×2
12 + 12 + 22
=
2×3
12 + 12 + 22 + 32
=
3×5
12 + 12 + 22 + 32 + 52
=
5×8
12 + 12 + 22 + 32 + 52 + 82
=
8×13
This picture actually is a convincing proof that the pattern will work for any number
of squares of Fibonacci numbers that we wish to sum. They always total to the
largest Fibonacci number used in the squares multiplied by the next Fibonacci number.
That is a bit of a mouthful to say - and to understand - so it is better to express
the relationship in the language of mathematics:
12 + 12 + 22 + 32 +
... + F(n)2 = F(n)F(n+1)
and it is true for ANY n from 1 upwards.
Here are some series that use the Fibonacci numbers. Compute a
few terms and see if you can spot the pattern, i.e. guess the formula for the
general term and write it down mathematically:
Keun Young Lee, a student at the Glenbrook North
High School in Chicago, told me of a generalisation of this.
Can you spot it too?
What is F(k)+F(k+1)+...+F(n)?
e.g. 5+8+13 (k=5 and n=7) is 26
3+5+8+13+21 (k=4 and n=8) is 50.
This problem will be the same as the first problem here if you let k=1 and this is
a useful check on your formula.
Can you find a connection between the terms of:
1x3, 2x5, 3x8, 5x13, ... , F(n-1)xF(n+1), ...
and the following series?
2x2, 3x3, 5x5, 8x8, ... , F(n)xF(n), ...
The connection was first noted by
Cassini (1625-1712) in 1680
and is called Cassini's Relation (see Knuth,
The Art of Computer Programming, Volume 1:Fundamental Algorithms,
section 1.2.8).
Try choosing different small values for a and b and finding some more
Pythagorean triangles.
Tick those triangles that are primitive and out a cross by those which
are multiples (of a primitive triangle).
Can you find the simple condition on a and b that tells us when the generated
Pythagorean triangle is primitive? [Hint: the condition has two parts:
i) what happens if both a and b have a common factor? ii) why are no
primitive triangles generated if a and b are both odd?].
Find all 16 primitive Pythagorean triangles with all 3 sides less than 100.
Use your list to generate all Pythagorean triangles with sides smaller
than 100. How many are there in all?
[Optional extra part: Can you devise a method to find which a and b generated
a given Pythagorean triangle?
Eg Given Pythagorean triangle 9,40,41 (and we can check that
92 + 402 = 412), how do we calculate that
it was generated from the values a=1, b=4?]
If you don't know how to begin, or get stuck,
look at the Hints and Tips page to get you going!
So try them for yourself. This is where Mathematics becomes more of an Art
than a Science, since you are relying on your intuition to "spot" the pattern.
No one is quite sure where this ability in humans comes from. It is
not easy to get a computer to do this (although Maple is quite good at it)
- and it may be something specifically
human that a computing machine can never really copy,
but no one is sure at present. Here are two references if you want to explore further
the arguments and ideas of why an electronic computer may or may not be able to
mimic a human brain:
Prof Roger Penrose's book
Shadows of the Mind published in 1994 by Oxford Press
makes interesting reading on this subject.
Dr. Math
has some interesting replies to questions about the Fibonacci series
and the Golden section together with a few more formulae for you to check out.
Fibonacci and Lucas numbers, and the Golden Section: Theory
and Applications, S Vajda, Dover reprint (2007).
This is a wonderful book - now back in print after many years - which is full of formulae on
the Fibonacci numbers and Phi. Do try and find it in your local college or
university library. It is well worth dipping in to if you are studying maths at
age 16 or beyond! Most of Vajda's formulae are available on my
Fibonacci, Phi and Lucas Numbers Formulae page too, with
some corrections of Vajda's (rare) errors.
Mathematical Mystery Tour by Mark Wahl, 1989, is full of many mathematical
investigations, illustrations, diagrams, tricks, facts, notes as well
as guides for teachers using the material. It is a great resource for
your own investigations.
icon means there is a
You do the maths... section of questions to start your own investigations.
calculator icon
indicates that there is a live interactive calculator in that section.
You do the maths...
.
(N) means the number of
primes between 1 and N
5) and Lucas(i) is
round(Phii). Dividing by sqrt(5) will merely adjust the scale - which does not matter.
Similarly, rounding will not affect the overall distribution of the digits in a large sample.Calculating probabilities.
We shall make a family tree of the rabbits but this time we shall be interested
only in the females and ignore any males in the population. If you like,
in the
diagram of the rabbit pairs shown here, assume that the rabbit on the left
of each pair is male (say)
and so the other is female. Now ignore the rabbit on the left in each pair!
simulation of a quincunx
showing each ball bouncing as it falls.
A common example is a triangle with sides s=3, t=4 and h=5:
Pythagorean Triples A F Horadam Fibonacci Quarterly vol 20 (1982) pages 121-122.
For instance, if the sides are 3 and 5, by Pythagoras' Theorem we have that the hypotenuse, h, is given by:
Let's look again at the Fibonacci squares and spiral
that we saw in the Fibonacci Spiral section of
the Fibonacci in Nature page. 
The Puzzling World of the Fibonacci Numbers
Fibonacci Home Page
The Golden Section - the Number and Its Geometry
© 1996-2016 Dr Ron Knott
